package LeetCode;

public class Code79_exist {

    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0
                || board[0].length == 0 || word == null || word.length() == 0){
            return false;
        }
        int m = board.length;
        int n = board[0].length;
        // 标记访问过的位置
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, 0, i, j)){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word,
                        int index, int i, int j) {
        if (index == word.length() - 1){
            return board[i][j] == word.charAt(index);
        }
        if (word.charAt(index) == board[i][j]){
            visited[i][j] = true;
            if (i - 1 >= 0 && !visited[i-1][j] && dfs(board, word, index + 1, i-1, j)){
                return true;
            }
            if (i + 1 < board.length && !visited[i+1][j] && dfs(board, word, index + 1, i+1, j)){
                return true;
            }
            if (j - 1 >= 0 && !visited[i][j-1] && dfs(board, word, index+1, i, j - 1)){
                return true;
            }
            if (j + 1 < board[0].length && !visited[i][j+1] && dfs(board, word, index+1, i, j + 1)){
                return true;
            }
            // 搜索完之后回溯的话需要重置
            visited[i][j] = false;
        }
        return false;
    }

    public static void main(String[] args) {
        Code79_exist code79_exist = new Code79_exist();
        char[][] board =
                new char[][]{{'A', 'B', 'C', 'E'},
                            {'S', 'F', 'C', 'S'},
                            {'A', 'D', 'E', 'E'}};
        System.out.println(code79_exist.exist(board, "ABCB"));
    }
}
